package com.zpself.module.算法练习.链表;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @author By ZengPeng
 * @Description 请判断一个链表是否为回文链表。
 * @date in  2021/1/20 19:13
 * @Modified By
 */
public class 力扣_234_回文链表 {
    public static void main(String[] args) {

        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(2);
        ListNode n4 = new ListNode(1);
        n1.next=n2;
        n2.next=n3;
        n3.next=n4;
        boolean listNode = myAnswer(null);
        boolean listNode2 = isPalindrome(n1);
        System.out.println(listNode);
        System.out.println(listNode2);

    }
    public static boolean myAnswer(ListNode head){
       ListNode old = head;
       Stack<Integer> val = new Stack<>();
        while (head!=null){
            val.push(head.val);
            head = head.next;
        }
        while (!val.isEmpty() ){
            if(old.val!= val.pop()) return false;
            old = old.next;
        }
        return true;
    }


    static boolean isPalindrome(ListNode head) {
        // 要实现 O(n) 的时间复杂度和 O(1) 的空间复杂度，需要翻转后半部分
        if (head == null || head.next == null)  return true;
        ListNode fast = head,slow = head;
        // 根据快慢指针，找到链表的中点
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 反转中间节点开始的链表
        ListNode slowReverse = null;
        slow =slow.next;
        while (slow!=null){
            ListNode next = slow.next;
            slow.next =slowReverse;
            slowReverse = slow;
            slow = next;
        }
        //对比
        while(slowReverse != null) {
            if (head.val != slowReverse.val)return false;
            head = head.next;
            slowReverse = slowReverse.next;
        }
        return true;
    }

    private static ListNode reverse(ListNode head){
        // 递归到最后一个节点，返回新的新的头结点
        ListNode result = null;
        while (head!=null){
            ListNode next = head.next;
            head.next =result;
            result = head;
            head = next;
        }
        return result;
    }
}
